/* Copyright (c) 2010, mitsuhisa.net
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 *
 *     * Redistributions of source code must retain the above copyright
 *       notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above
 *       copyright notice, this list of conditions and the following
 *       disclaimer in the documentation and/or other materials provided
 *       with the distribution.
 *     * Neither the name of the misuhisa.net nor the names of its
 *       contributors may be used to endorse or promote products derived
 *       from this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include <cassert>
#include "MemoryManager.hpp"
#include "HeapObject.hpp"

namespace nyu {

const size_t CHUNK_SIZE = (1024 * 8);

MemoryManager::MemoryManager() :
        heap_object_(0), total_allocated_(0), destruct_queue_(0),
        destruct_queue_last_(0), minor_gc_count_(0), major_gc_count_(0) {
    void* chunk = ::operator new(CHUNK_SIZE);
    HeapObject* p = reinterpret_cast<HeapObject*>(chunk);
    p->size_ = CHUNK_SIZE;
    p->refcnt_ = 0;
    p->prev_ = 0;
    p->next_ = 0;
    free_block_ = p;
    chunks_.push_back(chunk);
}

MemoryManager::~MemoryManager() {

}

HeapObject* MemoryManager::allocate(size_t size) {
    total_allocated_ += size;

    if (heap_object_ && heap_object_->refcnt_ == 0)
        heap_object_ = heap_object_->next_;

    if (size >= 255) {
        HeapObject* p = reinterpret_cast<HeapObject*>(::operator new(size));
        p->size_ = size;
        p->refcnt_ = 1;
        p->prev_ = 0;
        p->next_ = 0;
        p->setAlloced(true);
        return p;
    }

    if (size & (sizeof(long) - 1)) {
        size &= ~(sizeof(long) - 1);
        size += sizeof(long);
    }

    HeapObject* free_block = free_block_;
    while (free_block) {
        if (free_block->size_ >= size)
            break;
        free_block = free_block->next_;
    }

    if (!free_block) {
        minorGC();

        free_block = free_block_;
        while (free_block) {
            if (free_block->size_ >= size)
                break;
            free_block = free_block->next_;
        }

        if (!free_block) {
            if (chunks_.size() + 1 > chunks_.capacity())
                majorGC();

            free_block = free_block_;
            while (free_block) {
                if (free_block->size_ >= size)
                    break;
                free_block = free_block->next_;
            }

            if (!free_block) {
                void* chunk = ::operator new(CHUNK_SIZE);
                free_block = reinterpret_cast<HeapObject*>(chunk);
                free_block->size_ = CHUNK_SIZE;
                free_block->refcnt_ = 0;
                free_block->prev_ = 0;
                free_block->next_ = free_block_;
                if (free_block_)
                    free_block_->prev_ = free_block;
                free_block_ = free_block;
                chunks_.push_back(chunk);
            }
        }
    }

    if (free_block->size_ - size < sizeof(HeapObject)) {
        if (free_block->prev_)
            free_block->prev_->next_ = free_block->next_;
        else
            free_block_ = free_block->next_;
        if (free_block->next_)
            free_block->next_->prev_ = free_block->prev_;
    } else {
        char* pp = reinterpret_cast<char*>(free_block) + size;
        HeapObject* p = reinterpret_cast<HeapObject*>(pp);
        p->size_ = free_block->size_ - size;
        p->refcnt_ = 0;
        p->next_ = free_block->next_;
        if (free_block->prev_) {
            p->prev_ = free_block->prev_;
            free_block->prev_->next_ = p;
        } else {
            p->prev_ = 0;
            free_block_ = p;
        }
        if (p->next_)
            p->next_->prev_ = p;
    }

    free_block->size_ = size;
    free_block->refcnt_ = 1;
    free_block->prev_ = 0;
    free_block->next_ = heap_object_;
    if (heap_object_)
        heap_object_->prev_ = free_block;
    heap_object_ = free_block;

    return free_block;
}

void MemoryManager::minorGC() {
    ++minor_gc_count_;

    assert(!heap_object_ || heap_object_->refcnt_ != 0);

    destructObjects();

    char* pp = reinterpret_cast<char*>(chunks_.back());
    char* pe = pp + CHUNK_SIZE;

    HeapObject* free_block = free_block_;
    while (free_block) {
        if (reinterpret_cast<char*>(free_block) < pp
                || pe <= reinterpret_cast<char*>(free_block))
            break;
        free_block = free_block->next_;
    }

    HeapObject* start = 0;
    HeapObject* prev = 0;

    size_t i = 0;
    while (i < CHUNK_SIZE - sizeof(HeapObject)) {
        HeapObject* ho = reinterpret_cast<HeapObject*>(&pp[i]);

        if (ho->refcnt_ == 0) {
            if (!start)
                start = ho;

            if (prev) {
                if (reinterpret_cast<char*>(prev) + prev->size_
                        == reinterpret_cast<char*>(ho)) {
                    prev->size_ += ho->size_;
                    goto NEXT;
                } else {
                    prev->next_ = ho;
                }
            }

            ho->prev_ = prev;
            ho->next_ = 0;
            prev = ho;
        }

        NEXT:

        if (ho->size_ == 0)
            break;

        i += ho->size_;
    }

    if (prev)
        prev->next_ = free_block;
    if (free_block)
        free_block->prev_ = prev;
    if (start)
        free_block_ = start;
}

void MemoryManager::majorGC() {
    ++major_gc_count_;

    class DecrTmpRefcntFunc : public HeapObject::EachChildrenFunc {
    public:
        virtual void operator()(HeapObject* p) const {
            assert(p->tmp_refcnt_);

            --p->tmp_refcnt_;
        }
    };

    class IncrTmpRefcntFunc : public HeapObject::EachChildrenFunc {
    public:
        IncrTmpRefcntFunc(HeapObject* owner, HeapObject** pp) :
            owner_(owner), pp_(pp) {
        }

        virtual void operator()(HeapObject* p) const {
            if (p->tmp_refcnt_ == 0 && owner_->next_ != p) {
                // remove from heap_object_
                if (p->prev_)
                    p->prev_->next_ = p->next_;
                else
                    *pp_ = p->next_;
                if (p->next_)
                    p->next_->prev_ = p->prev_;

                // add to next_
                p->prev_ = owner_;
                p->next_ = owner_->next_;
                if (owner_->next_)
                    owner_->next_->prev_ = p;
                owner_->next_ = p;
            }

            ++p->tmp_refcnt_;
        }

    private:
        HeapObject* owner_;
        HeapObject** pp_;
    };

    assert(!heap_object_ || heap_object_->refcnt_ != 0);

    destructObjects();

    for (HeapObject* ho = heap_object_; ho; ho = ho->next_) {
        ho->tmp_refcnt_ = ho->refcnt_;
    }

    for (HeapObject* ho = heap_object_; ho; ho = ho->next_) {
        ho->eachChildren(DecrTmpRefcntFunc());
    }

    for (HeapObject* ho = heap_object_; ho; ho = ho->next_) {
        if (ho->tmp_refcnt_ > 0)
            ho->eachChildren(IncrTmpRefcntFunc(ho, &heap_object_));
    }

    for (HeapObject* ho = heap_object_, *hon = 0; ho; ho = hon) {
        hon = ho->next_;
        if (ho->tmp_refcnt_ == 0) {
            ho->refcnt_ = 0;
            addDestructQueue(ho);
        }
    }

    assert(!heap_object_ || heap_object_->refcnt_ != 0);

    destructObjects();

    HeapObject* free_block = 0;

    typedef std::vector<void*>::iterator iter;
    for (iter it = chunks_.begin(), end = chunks_.end(); it != end; ++it) {
        HeapObject* start = 0;
        HeapObject* prev = 0;

        char* p = reinterpret_cast<char*>(*it);
        size_t i = 0;
        while (i < CHUNK_SIZE - sizeof(HeapObject)) {
            HeapObject* ho = reinterpret_cast<HeapObject*>(&p[i]);

            if (ho->refcnt_ == 0) {
                if (!start)
                    start = ho;

                if (prev) {
                    if (reinterpret_cast<char*>(prev) + prev->size_
                            == reinterpret_cast<char*>(ho)) {
                        prev->size_ += ho->size_;
                        goto NEXT;
                    } else {
                        prev->next_ = ho;
                    }
                }

                ho->prev_ = prev;
                ho->next_ = 0;
                prev = ho;
            }

            NEXT:

            if (ho->size_ == 0)
                break;

            i += ho->size_;
        }

        if (prev)
            prev->next_ = free_block;
        if (free_block)
            free_block->prev_ = prev;
        if (start)
            free_block = start;
    }

    free_block_ = free_block;
}

MemoryManager& MemoryManager::getInstance() {
    static MemoryManager instance;
    return instance;
}

size_t MemoryManager::countAlivedObjects() const {
    size_t n = 0;
    for (HeapObject* o = heap_object_; o; o = o->next_) {
        ++n;
    }
    return n;
}

void MemoryManager::addDestructQueue(HeapObject* p) {
    assert(p && p->refcnt_ == 0);

    if (!p->isAlloced()) {
        if (p->prev_)
            p->prev_->next_ = p->next_;
        else
            heap_object_ = p->next_;
        if (p->next_)
            p->next_->prev_ = p->prev_;
    }

    p->next_ = 0;

    if (destruct_queue_) {
        assert(destruct_queue_last_);

        destruct_queue_last_->next_ = p;
        destruct_queue_last_ = p;
    } else {
        destruct_queue_ = destruct_queue_last_ = p;
    }
}

void MemoryManager::destructObjects() {
    HeapObject* ho = destruct_queue_;
    HeapObject* next = 0;

    while (ho) {
        ho->refcnt_ = 0;

        if (ho->isAlloced()) {
            ho->~HeapObject();
            next = ho->next_;
            ::operator delete(ho);
        } else {
            ho->~HeapObject();
            next = ho->next_;
        }

        ho = next;
    }

    destruct_queue_ = destruct_queue_last_ = 0;
}

}
